package dp

import "math"

func minPathSumDFS(grid [][]int) int {
	return minDist(grid, len(grid)-1, len(grid[len(grid)-1])-1)
}

// dist(i,j) = grid[i][j] + min(grid[i-1][j],grid[i][j-1])
func minDist(grid [][]int, row, col int) int {
	if row < 0 || col < 0 {
		return math.MaxInt
	}
	if row == 0 && col == 0 {
		return grid[0][0]
	}
	return grid[row][col] + min(minDist(grid, row-1, col), minDist(grid, row, col-1))
}

func optimizeMinDist(grid [][]int, row, col int, mem *[][]int) int {
	if row < 0 || col < 0 {
		return math.MaxInt
	}
	// 错误写法，可能会有意料之外的情况，最好的记录方式是只记录当次的结果
	//var a, b int
	//if a = (*mem)[row-1][col]; a == -1 {
	//	a = minDist(grid, row-1, col)
	//	(*mem)[row-1][col] = a
	//}
	//
	//if b = (*mem)[row][col-1]; b == -1 {
	//	b = minDist(grid, row, col-1)
	//	(*mem)[row][col-1] = b
	//}
	//
	//return grid[row][col] + min(a, b)
	if val := (*mem)[row][col]; val != -1 {
		return val
	}
	return grid[row][col] + min(optimizeMinDist(grid, row-1, col, mem), optimizeMinDist(grid, row, col-1, mem))
}

func minDistDp(grid [][]int, rows, cols int) int {
	//递推公式: dp[row][col] = grid[row][col] + min(dp[row-1][col], dp[row][col-1])
	dp := make([][]int, rows)
	for i := range dp {
		dp[i] = make([]int, cols)
	}
	dp[0][0] = 0

	//填充首行
	for i := 1; i < len(grid[0]); i++ {
		dp[0][i] = grid[0][i] + dp[0][i-1]
	}

	//填充首列
	for i := 1; i < len(grid); i++ {
		dp[i][0] = dp[i-1][0] + grid[i][0]
	}

	for row := 1; row < rows; row++ {
		for col := 1; col < cols; col++ {
			dp[row][col] = grid[row][col] + min(dp[row-1][col], dp[row][col-1])
		}
	}
	return dp[rows-1][cols-1]
}

// TODO 优化空间，写注释
func optimizeMinDistDp(grid [][]int, rows, cols int) int {
	dp := make([]int, cols)
	dp[0] = grid[0][0]
	for i := 1; i < len(dp); i++ {
		dp[i] = dp[i-1] + grid[0][i]
	}
	for i := 1; i < rows; i++ {
		//更改首列
		dp[0] = grid[i][0]
		for j := 1; j < cols; j++ {
			dp[j] = grid[i][j] + min(dp[j], dp[j-1])
		}
	}
	return dp[cols-1]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
